﻿#pragma once
#include <vector>
#include <algorithm>
#include <vector>

#include "MathUtils.h"

namespace sim_geo_alg {
	struct GPoint {
		double x;
		double y;
	};

	struct GSegment {
		GPoint aoint;
		GPoint boint;
	};

	struct GWire {
		std::vector<GPoint> vertices;
	};

	struct GPolygon {
		std::vector<GPoint> vertices;
	};

	/**
	 * \brief  is lift side
	 * \param x1
	 * \param y1
	 * \param x2
	 * \param y2
	 * \param x3
	 * \param y3
	 * \return right <0 left > 0  on line = 0
	 */
	inline double is_left(const double x1, const double y1, const double x2, const double y2, const double x3,
	                      const double y3) {
		return (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);
	}

	inline double p_is_left_seg(const GSegment& seg, const GPoint& p) {
		return (seg.boint.x - seg.aoint.x) * (p.y - seg.aoint.y) - (p.x - seg.aoint.x) * (seg.boint.y - seg.aoint.y);
	}

	/**
	 * \brief segment and segment intersect
	 * 这种相交是指的不包括线段的端点那种相交,
	 * \return intersect true
	 */
	inline bool is_inter(const GSegment& seg1, const GSegment& seg2, const double ep) {
		double res1 = p_is_left_seg(seg1, seg2.aoint);
		double res2 = p_is_left_seg(seg1, seg2.boint);
		if (MathUtils::EqualZero(res1, ep) || MathUtils::EqualZero(res2, ep)) {
			return false;
		}
		double res_seg1 = res1 * res2;
		if (MathUtils::Less<double>(res_seg1, 0.0, ep)) {
			res1 = p_is_left_seg(seg2, seg1.aoint);
			res2 = p_is_left_seg(seg2, seg1.boint);
			if (MathUtils::EqualZero(res1, ep) || MathUtils::EqualZero(res2, ep)) {
				return false;
			}
			double res_seg2 = res1 * res2;
			if (MathUtils::Less<double>(res_seg2, 0.0, ep)) {
				return true;
			}
		}
		return false;
	}


	/**
	 * \brief 完全不相交 false ,有相交的可能性 true
	 * \param seg1 x1 y1 x2 y2
	 * \param seg2 x3 y3 x4 y4
	 * \return
	 */
	inline bool quick_deny_inter(const GSegment& seg1, const GSegment& seg2, const double ep) {
		double minX1 = seg1.boint.x;
		double maxX1 = seg1.aoint.x;
		if (seg1.aoint.x < seg1.boint.x) {
			minX1 = seg1.aoint.x;
			maxX1 = seg1.boint.x;
		}
		double minY1 = seg1.boint.y;
		double maxY1 = seg1.aoint.y;
		if (seg1.aoint.y < seg1.boint.y) {
			minY1 = seg1.aoint.y;
			maxY1 = seg1.boint.y;
		}

		if (MathUtils::Greater<double>(seg2.aoint.x, maxX1, ep) && MathUtils::Greater<double>(seg2.boint.x, maxX1, ep)) {
			return false;
		}
		if (MathUtils::Less<double>(seg2.aoint.x, minX1, ep) && MathUtils::Less<double>(seg2.boint.x, minX1, ep)) {
			return false;
		}
		if (MathUtils::Greater<double>(seg2.aoint.y, maxY1, ep) && MathUtils::Greater<double>(seg2.boint.y, maxY1, ep)) {
			return false;
		}
		if (MathUtils::Less<double>(seg2.aoint.y, minY1, ep) && MathUtils::Less<double>(seg2.boint.y, minY1, ep)) {
			return false;
		}
		return true;
	}

	inline bool segs_inter_segs(const std::vector<GSegment>& s1egs, const std::vector<GSegment>& seg2s, const double ep) {
		for (const auto& segItem : s1egs) {
			for (const auto& metIges : seg2s) {
				bool b = is_inter(segItem, metIges, ep);
				if (b) {
					return true;
				}
			}
		}
		return false;
	}

	inline std::vector<GSegment> wire_to_segments(const GWire& ori) {
		std::vector<GSegment> segs;
		segs.reserve(ori.vertices.size() - 1);
		for (int i = 0; i < ori.vertices.size() - 1; ++i) {
			GSegment g;
			g.aoint = ori.vertices[i];
			g.boint = ori.vertices[i + 1];
			segs.push_back(g);
		}
		return segs;
	}

	inline bool p_equal_p(const GPoint& p, const GPoint& b, const double epsilon) {
		return (
			MathUtils::Equal<double>(p.x, b.x, epsilon) &&
			MathUtils::Equal<double>(p.y, b.y, epsilon)
		);
	}

	inline double p_sq_dis_p(const GPoint& p, const GPoint& b) {
		return (p.x - b.x) * (p.x - b.x) + (p.y - b.y) * (p.y - b.y);
	}

	inline bool point_on_end(const GSegment& s, const GPoint p, const double ep) {
		return p_equal_p(s.aoint, p, ep) || p_equal_p(s.boint, p, ep);
	}

	inline bool p_on_seg(const GSegment& s, const GPoint p, const double ep) {
		if (point_on_end(s, p, ep)) return true;
		if ((MathUtils::LessEqual<double>(p.y, s.aoint.y, ep) &&
				MathUtils::GreaterEqual<double>(p.y, s.boint.y, ep)) ||
			(MathUtils::GreaterEqual<double>(p.y, s.aoint.y, ep) &&
				MathUtils::LessEqual<double>(p.y, s.boint.y, ep))
		) {
			if (MathUtils::Equal<double>(s.aoint.y, s.boint.y, ep)) {
				return (MathUtils::Less(p.x, s.aoint.x, ep) != MathUtils::Less(p.x, s.boint.x, ep));
			}
			const auto pX = ((s.aoint.x - s.boint.x) * (p.y - s.boint.y)) / (s.aoint.y - s.boint.y) + s.boint.x;
			if (MathUtils::Equal<double>(p.x, pX, ep)) return true;
		}
		return false;
	}

	inline bool plg_contain_p(const GPolygon& plg, const GPoint& point, const double ep) {
		const auto n = plg.vertices.size();
		const auto x = point.x;
		const auto y = point.y;
		auto x0 = plg.vertices[n - 1].x;
		auto y0 = plg.vertices[n - 1].y;
		auto x1 = plg.vertices[0].x;
		auto y1 = plg.vertices[0].y;
		auto inside = false;

		for (auto i = 0; i < n; ++i) {
			x1 = plg.vertices[i].x;
			y1 = plg.vertices[i].y;
			if (y1 > y != y0 > y) {
				if (x < ((x0 - x1) * (y - y1) / (y0 - y1) + x1)) {
					inside = !inside;
				}
			}
			x0 = x1;
			y0 = y1;
		}

		return inside;
	}

	inline bool p_on_wire(const GWire& wire, const GPoint& point, const double ep) {
		const auto segs = wire_to_segments(wire);
		for (auto seg : segs) {
			if (p_on_seg(seg, point, ep)) {
				return true;
			}
		}
		return false;
	}


	inline bool p_left_wire(const GWire& wire, const GPoint& point, const double ep) {
		if (p_on_wire(wire, point, ep)) {
			return false;
		}
		const auto front = wire.vertices.front();
		const auto back = wire.vertices.back();
		if (MathUtils::Equal(front.y, point.y, ep)) {
			if (MathUtils::Less(point.x, front.x, ep)) {
				return true;
			}
		}
		if (MathUtils::Equal(back.y, point.y, ep)) {
			if (MathUtils::Less(point.x, back.x, ep)) {
				return true;
			}
		}
		const auto n = wire.vertices.size();
		const auto x = point.x;
		const auto y = point.y;
		auto x0 = wire.vertices[0].x;
		auto y0 = wire.vertices[0].y;
		auto x1 = wire.vertices[1].x;
		auto y1 = wire.vertices[1].y;

		for (auto i = 1; i < n; ++i) {
			x1 = wire.vertices[i].x;
			y1 = wire.vertices[i].y;
			if ((y1 > y) != (y0 > y)) {
				const auto inter = ((x0 - x1) * (y - y1) / (y0 - y1) + x1);
				if (x < inter) {
					return true;
				}
			}
			x0 = x1;
			y0 = y1;
		}

		return false;
	}

	inline std::vector<GPoint> seg_cut_ps(const GSegment& seg, const std::vector<GPoint>& vs, const double ep) {
		std::vector<GPoint> ps;
		for (const auto& v : vs) {
			if (p_on_seg(seg, v, ep)) {
				ps.push_back(v);
			}
		}
		const auto f = seg.aoint;
		std::sort(ps.begin(), ps.end(), [f](const GPoint& p1, const GPoint& p2) {
			return p_sq_dis_p(p1, f) < p_sq_dis_p(p2, f);
		});
		return ps;
	}


	/**
	* \brief 线段在多边形内，包括边界，两个点都在多边形内，且线段被多边形分割成多段后的中点还是在多半形内
	 * \param plg 
	 * \param seg 
	 * \param ep 
	 * \return 
	 */
	inline bool seg_inside_plg(const GPolygon& plg, const GSegment& seg, const double ep) {
		GPoint prev = seg.aoint;
		auto ps = seg_cut_ps(seg, plg.vertices, ep);
		ps.push_back(seg.boint);
		int i = 0;
		while (i < ps.size()) {
			const auto next = ps[i];
			const auto center = GPoint{
				(prev.x + next.x) * 0.5,
				(prev.y + next.y) * 0.5
			};
			prev = next;
			if (!plg_contain_p(plg, center, ep)) {
				return false;
			}
		}
		return false;
	}

	inline bool seg_left_wire(const GWire& wire, const GSegment& seg, const double ep) {
		GPoint prev = seg.aoint;
		auto ps = seg_cut_ps(seg, wire.vertices, ep);
		ps.push_back(seg.boint);
		int i = 0;
		while (i < ps.size()) {
			const auto next = ps[i];
			const auto center = GPoint{
				(prev.x + next.x) * 0.5,
				(prev.y + next.y) * 0.5
			};
			if (p_left_wire(wire, center, ep)) {
				return true;
			}
			prev = next;
			i++;
		}
		return false;
	}

	inline bool wire_inter_wire(const GWire& w1re, const GWire& e2iw, const double ep) {
		const auto s1egs = wire_to_segments(w1re);
		const auto seg2s = wire_to_segments(e2iw);
		return segs_inter_segs(s1egs, seg2s, ep);
	}

	/**
	 * \brief wire2 只有一部分在 wire1 左侧就算 true
	 * \param wire1 
	 * \param wire2 
	 * \param ep 
	 * \return 
	 */
	inline bool wire_left_wire(const GWire& wire1, const GWire& wire2, const double ep) {
		const auto segs = wire_to_segments(wire2);
		const auto s1egs = wire_to_segments(wire1);
		bool inter = segs_inter_segs(segs, s1egs, ep);
		if (inter) {
			return true;
		}
		for (const auto& seg : segs) {
			bool b = seg_left_wire(wire1, seg, ep);
			if (b) {
				return true;
			}
		}
		return false;
	}


	inline double polygonarea(std::vector<GPoint>& polygon) {
		const int N = polygon.size() - 1;
		double area = 0;
		for (int i = 0; i < N; i++) {
			area += polygon[i].x * polygon[i + 1].y - polygon[i].y * polygon[i + 1].x;
		}
		area += polygon.back().x * polygon.front().y - polygon.back().y * polygon.front().x;
		area *= 0.5;
		return (area < 0 ? -area : area);
	}
}
